/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 也是动态规划--只是把dp[i]变为了两个变量
// 美其名曰：滚动数组法
class Solution {
public:
    int climbStairs(int n) {
        if(n == 1){return 1;}
        if(n == 2){return 2;}
        int a = 1, b = 2, temp;
        for(int i = 3; i <= n; i++){
            temp = a;
            a = b;
            b = temp + b;
        }
        return b;
    }
};
// // 分治法
// class Solution {
// public:
//     int climbStairs(int n) {
//         if(n==0) return 0;
//         if(n==1) return 1;
//         if(n==2) return 2;
//         int result = checkNum(n);
//         return result;
//     }
// public:
//     int nums=0;  // 几种方法
//     int checkNum(int n) {
//         if(n<=0) return 0;
//         if(n==1) return 1;
//         if(n==2) return 2;
//         this->nums = this->nums + checkNum(n-2);
//         this->nums = this->nums + checkNum(n-1);
//         return this->nums;
//     }
// };


int main(int argc, const char** argv) {
    Solution solu = Solution();
    cout << solu.climbStairs(3) << endl;

    return 0;
}